package topic.string;

import java.util.HashSet;
import java.util.Hashtable;
import java.util.Map;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 */
public class LengthOfLongestSubstring {
    public static void main(String[] args) {
        String s = "abcabcbb";
        lengthOfLongestSubstring(s);
    }

    /**
     * 滑动窗口
     * @param s
     * @return
     */
    private static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int i = 0;
        int j = 0;
        int max = 0;
        for (;j < s.length();) {
            if (!set.contains(s.charAt(j))) {
                // 滑动右边界
                set.add(s.charAt(j++));
                max = Math.max(max, j - i);
            } else {
                // 滑动左边界
                set.remove(s.charAt(i++));
            }
        }
        return max;
    }

    private static int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> map = new Hashtable<>();
        int max = 0;
        for (int i = 0, j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                // 滑动左边界
                i = Math.max(i, map.get(s.charAt(j)));
            }
            map.put(s.charAt(j), j + 1);
            max = Math.max(max, j - i + 1);
        }
        return max;
    }

}
